package algorithm.sort;

import java.util.Arrays;

/**
 * 快速排序
 * 
 * @author jyzjyz12@163.com
 * @since 2017年2月27日 上午10:26:08
 */
public class QuickSortTest1 {
    public static void main(String[] args) {
        int[] arr1 = { 4, 7, 5, 6, 1, 3, 8 };
        int[] arr2 = { 7, 6, 5, 4, 3, 2, 1 };
        int[] arr3 = { 5, 9, 3, 7, 8, 6, 1, 2, 4 };
        int[] arr4 = { 13, 2, 5, 4, 88, 76, 68, 87, 55, 88, 88, 77, 67, 99, 100, 5, 53, 52, 51, 66 };
        sort(arr1);
        sort(arr2);
        sort(arr3);
        sort(arr4);
        System.out.println(Arrays.toString(arr1));
        System.out.println(Arrays.toString(arr2));
        System.out.println(Arrays.toString(arr3));
        System.out.println(Arrays.toString(arr4));
    }

    public static int[] getSortedArr(int[] arr) {
        int[] result = Arrays.copyOf(arr, arr.length);
        sort(result);
        return result;
    }

    public static void sort(int[] arr) {
        sortInternal(arr, 0, arr.length - 1);
    }

    private static void sortInternal(int[] arr, int low, int high) {
        // 当然只有1个元素的时候就不需要排序了,这里low>=而不是=是因为下面
        // sortInternal(arr, currPosition + 1, high);
        // currPositon+1可能会导致low=hight的时候low+1>high
        if (low >= high) { // 这个if是递归结束条件
            return;
        } else { // 递归分解条件
            int currPosition = sortOnce(arr, low, high); // 得到一个基准值的最终位置,左边的数字都比它小,右边都比它大
            sortInternal(arr, low, currPosition - 1); // 左边的数字继续递归进行快速排序
            sortInternal(arr, currPosition + 1, high);// 右边的数字继续递归进行快速排序
        }
    }

    /**
     * 一轮排序
     * 
     * @param arr
     *            待排序数组
     * @param low
     *            头指针
     * @param high
     *            尾指针
     * @return 基准的位置
     */
    private static int sortOnce(int[] arr, int low, int high) {
        int key = arr[low]; // 基准有很多种选择方法,取最左边的元素只是一种方法
        while (high > low) {// 每一轮终止条件是2个指针重合
            while (high > low) { // 每一轮开始先移动尾指针
                if (arr[high] > key) { // high的数字比基准大
                    high--; // high向前移动
                } else {
                    swap(arr, low, high); // 交换low和high位置的数字
                    low++;// 交换过位置了不用再次判断,所以low++
                    break;// 准备开始头指针的移动
                }
            }
            while (high > low) {// 头指针和尾指针交换过位置的话再开始移动头指针,再交换的话继续下个外层while循环继续移动头指针
                if (arr[low] < key) { // low的数字比基准小
                    low++;// low向后移动
                } else {
                    swap(arr, low, high);// 交换low和high位置的数字
                    high--;// 交换过位置了不用再次判断,所以high--
                    break;// 准备开始尾指针的移动
                }
            }
        }
        return low;// high和low重合,返回哪个都一样
    }

    /**
     * 交换数字high和low位置的2个数字
     * 
     * @param arr
     * @param p1
     * @param p2
     */
    private static void swap(int[] arr, int p1, int p2) {
        int temp = arr[p1];
        arr[p1] = arr[p2];
        arr[p2] = temp;
    }
}
